package aInterview.xiaomi;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Test {

    List<Integer> path=new LinkedList<>();
    int cursum=0;
    public int chooseBestSum(int t, int k, List<Integer> ls) {
        // 在这⾥写代码
        backtrack(ls,0,0,t,k);
        return  cursum ;
    }

    public   void backtrack(List<Integer> ls,int start,int sum,int
            t,int k){
        if(sum>t){
            return;
        }
        if(path.size()==k&&sum<=t){
            cursum=Math.max(cursum,sum);
        }
        for(int i=start;i<ls.size();i++){
            sum+=ls.get(i);
            path.add(ls.get(i));
            if(sum<t){
                backtrack(ls,i+1,sum,t,k);
            }
            path.remove(path.size()-1);
            sum-=ls.get(i);
        }
    }


    public static void main(String[] args) {
        Test test = new Test();
        ArrayList<Integer> list = new ArrayList<>();
        list.add(50);
        list.add(55);
        list.add(56);
        list.add(57);
        list.add(58);
        test.chooseBestSum(163,3,list);
        System.out.println(test.cursum);

    }
}
